package org.apache.lucene.index;

/**
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

import java.io.IOException;
import java.util.Arrays;

import org.apache.lucene.store.BufferedIndexInput;
import org.apache.lucene.store.IndexInput;

/**
 * This abstract class reads skip lists with multiple levels.
 * 
 * See {@link MultiLevelSkipListWriter} for the information about the encoding 
 * of the multi level skip lists. 
 * 
 * Subclasses must implement the abstract method {@link #readSkipData(int, IndexInput)}
 * which defines the actual format of the skip data.
 */
abstract class MultiLevelSkipListReader {
    // the maximum number of skip levels possible for this index
    private int maxNumberOfSkipLevels;

    // number of levels in this skip list
    private int numberOfSkipLevels;

    // Expert: defines the number of top skip levels to buffer in memory.
    // Reducing this number results in less memory usage, but possibly
    // slower performance due to more random I/Os.
    // Please notice that the space each level occupies is limited by
    // the skipInterval. The top level can not contain more than
    // skipLevel entries, the second top level can not contain more
    // than skipLevel^2 entries and so forth.
    private int numberOfLevelsToBuffer = 1;

    private int docCount;
    private boolean haveSkipped;

    private IndexInput[] skipStream; // skipStream for each level
    private long skipPointer[]; // the start pointer of each skip level
    private int skipInterval[]; // skipInterval of each level
    private int[] numSkipped; // number of docs skipped per level

    private int[] skipDoc; // doc id of current skip entry per level 
    private int lastDoc; // doc id of last read skip entry with docId <= target
    private long[] childPointer; // child pointer of current skip entry per level
    private long lastChildPointer; // childPointer of last read skip entry with docId <= target

    private boolean inputIsBuffered;

    public MultiLevelSkipListReader(IndexInput skipStream, int maxSkipLevels, int skipInterval) {
        this.skipStream = new IndexInput[maxSkipLevels];
        this.skipPointer = new long[maxSkipLevels];
        this.childPointer = new long[maxSkipLevels];
        this.numSkipped = new int[maxSkipLevels];
        this.maxNumberOfSkipLevels = maxSkipLevels;
        this.skipInterval = new int[maxSkipLevels];
        this.skipStream[0] = skipStream;
        this.inputIsBuffered = (skipStream instanceof BufferedIndexInput);
        this.skipInterval[0] = skipInterval;
        for (int i = 1; i < maxSkipLevels; i++) {
            // cache skip intervals
            this.skipInterval[i] = this.skipInterval[i - 1] * skipInterval;
        }
        skipDoc = new int[maxSkipLevels];
    }

    /** Returns the id of the doc to which the last call of {@link #skipTo(int)}
     *  has skipped.  */
    int getDoc() {
        return lastDoc;
    }

    /** Skips entries to the first beyond the current whose document number is
     *  greater than or equal to <i>target</i>. Returns the current doc count. 
     */
    int skipTo(int target) throws IOException {
        if (!haveSkipped) {
            // first time, load skip levels
            loadSkipLevels();
            haveSkipped = true;
        }

        // walk up the levels until highest level is found that has a skip
        // for this target
        int level = 0;
        while (level < numberOfSkipLevels - 1 && target > skipDoc[level + 1]) {
            level++;
        }

        while (level >= 0) {
            if (target > skipDoc[level]) {
                if (!loadNextSkip(level)) {
                    continue;
                }
            } else {
                // no more skips on this level, go down one level
                if (level > 0 && lastChildPointer > skipStream[level - 1].getFilePointer()) {
                    seekChild(level - 1);
                }
                level--;
            }
        }

        return numSkipped[0] - skipInterval[0] - 1;
    }

    private boolean loadNextSkip(int level) throws IOException {
        // we have to skip, the target document is greater than the current
        // skip list entry        
        setLastSkipData(level);

        numSkipped[level] += skipInterval[level];

        if (numSkipped[level] > docCount) {
            // this skip list is exhausted
            skipDoc[level] = Integer.MAX_VALUE;
            if (numberOfSkipLevels > level)
                numberOfSkipLevels = level;
            return false;
        }

        // read next skip entry
        skipDoc[level] += readSkipData(level, skipStream[level]);

        if (level != 0) {
            // read the child pointer if we are not on the leaf level
            childPointer[level] = skipStream[level].readVLong() + skipPointer[level - 1];
        }

        return true;

    }

    /** Seeks the skip entry on the given level */
    protected void seekChild(int level) throws IOException {
        skipStream[level].seek(lastChildPointer);
        numSkipped[level] = numSkipped[level + 1] - skipInterval[level + 1];
        skipDoc[level] = lastDoc;
        if (level > 0) {
            childPointer[level] = skipStream[level].readVLong() + skipPointer[level - 1];
        }
    }

    void close() throws IOException {
        for (int i = 1; i < skipStream.length; i++) {
            if (skipStream[i] != null) {
                skipStream[i].close();
            }
        }
    }

    /** initializes the reader */
    void init(long skipPointer, int df) {
        this.skipPointer[0] = skipPointer;
        this.docCount = df;
        Arrays.fill(skipDoc, 0);
        Arrays.fill(numSkipped, 0);
        Arrays.fill(childPointer, 0);

        haveSkipped = false;
        for (int i = 1; i < numberOfSkipLevels; i++) {
            skipStream[i] = null;
        }
    }

    /** Loads the skip levels  */
    private void loadSkipLevels() throws IOException {
        numberOfSkipLevels = docCount == 0 ? 0 : (int) Math.floor(Math.log(docCount) / Math.log(skipInterval[0]));
        if (numberOfSkipLevels > maxNumberOfSkipLevels) {
            numberOfSkipLevels = maxNumberOfSkipLevels;
        }

        skipStream[0].seek(skipPointer[0]);

        int toBuffer = numberOfLevelsToBuffer;

        for (int i = numberOfSkipLevels - 1; i > 0; i--) {
            // the length of the current level
            long length = skipStream[0].readVLong();

            // the start pointer of the current level
            skipPointer[i] = skipStream[0].getFilePointer();
            if (toBuffer > 0) {
                // buffer this level
                skipStream[i] = new SkipBuffer(skipStream[0], (int) length);
                toBuffer--;
            } else {
                // clone this stream, it is already at the start of the current level
                skipStream[i] = (IndexInput) skipStream[0].clone();
                if (inputIsBuffered && length < BufferedIndexInput.BUFFER_SIZE) {
                    ((BufferedIndexInput) skipStream[i]).setBufferSize((int) length);
                }

                // move base stream beyond the current level
                skipStream[0].seek(skipStream[0].getFilePointer() + length);
            }
        }

        // use base stream for the lowest level
        skipPointer[0] = skipStream[0].getFilePointer();
    }

    /**
     * Subclasses must implement the actual skip data encoding in this method.
     *  
     * @param level the level skip data shall be read from
     * @param skipStream the skip stream to read from
     */
    protected abstract int readSkipData(int level, IndexInput skipStream) throws IOException;

    /** Copies the values of the last read skip entry on this level */
    protected void setLastSkipData(int level) {
        lastDoc = skipDoc[level];
        lastChildPointer = childPointer[level];
    }

    /** used to buffer the top skip levels */
    private final static class SkipBuffer extends IndexInput {
        private byte[] data;
        private long pointer;
        private int pos;

        SkipBuffer(IndexInput input, int length) throws IOException {
            super("SkipBuffer on " + input);
            data = new byte[length];
            pointer = input.getFilePointer();
            input.readBytes(data, 0, length);
        }

        @Override
        public void close() throws IOException {
            data = null;
        }

        @Override
        public long getFilePointer() {
            return pointer + pos;
        }

        @Override
        public long length() {
            return data.length;
        }

        @Override
        public byte readByte() throws IOException {
            return data[pos++];
        }

        @Override
        public void readBytes(byte[] b, int offset, int len) throws IOException {
            System.arraycopy(data, pos, b, offset, len);
            pos += len;
        }

        @Override
        public void seek(long pos) throws IOException {
            this.pos = (int) (pos - pointer);
        }

    }
}
